//给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。 
//
// 示例: 
//
// 输入:[1,2,3,null,5,null,4]
//输出:[1, 3, 4]
//解释:
//
//   1            <---
// /   \
//2     3         <---
// \     \
//  5     4       <---
// 
// Related Topics 树 深度优先搜索 广度优先搜索 
// 👍 316 👎 0

package leetcode.editor.cn;

import common.bean.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * Java：二叉树的右视图
 *
 * @author changgui
 */
@SuppressWarnings("all")
public class P199_BinaryTreeRightSideView {
    public static void main(String[] args) {
        Solution solution = new P199_BinaryTreeRightSideView().new Solution();
        // TODO 此处开始你的表演

    }

    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * 深度优先
     */
    class Solution {
        List<Integer> list = new ArrayList<>();

        public List<Integer> rightSideView(TreeNode root) {
            traverse(root, 0);
            return list;
        }

        private void traverse(TreeNode root, int depth) {
            if (root == null) {
                return;
            }
            if (depth == list.size()) {
                list.add(root.val);
            }
            depth++;
            traverse(root.right, depth);
            traverse(root.left, depth);
        }
    }
    ///**
    // * 广度优先，每行的最后一个
    // */
    //class Solution {
    //    public List<Integer> rightSideView(TreeNode root) {
    //        List<Integer> list = new ArrayList<>();
    //        if (root == null) {
    //            return list;
    //        }
    //        Deque<TreeNode> deque = new ArrayDeque<>();
    //        deque.addFirst(root);
    //        while (!deque.isEmpty()) {
    //            int size = deque.size();
    //            for (int i = 0; i < size; i++) {
    //                TreeNode treeNode = deque.removeLast();
    //                if(treeNode.left != null) {
    //                    deque.addFirst(treeNode.left);
    //                }
    //                if(treeNode.right != null) {
    //                    deque.addFirst(treeNode.right);
    //                }
    //                if(i == size - 1) {
    //                    list.add(treeNode.val);
    //                }
    //            }
    //        }
    //        return list;
    //    }
    //}
    //leetcode submit region end(Prohibit modification and deletion)

}